Programmable logic devices (PLDs) are a well-known type of integrated circuit that can be programmed to perform specified logic functions. For example, one type of PLD, the field programmable gate array (FPGA), typically includes a centrally-located array of configurable logic blocks (CLBs) surrounded by a ring of programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a programmable interconnect structure.
Some advanced FPGAs include more than one type of logic block in the centrally-located array. For example, the Xilinx Virtex®-II FPGA includes blocks of Random Access Memory (RAM) and blocks implementing multiplier functions. (The Xilinx Virtex-II FPGA is described in detail in pages 33–75 of the “Virtex-II Platform FPGA Handbook”, published January, 2001, available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124, which pages are incorporated herein by reference.)
The CLBs, IOBs, interconnect, and other logic blocks of an FPGA are typically programmed by loading a stream of configuration data (bitstream) into internal configuration memory cells that define how the logic blocks and interconnect are configured. The configuration data can be read from memory (e.g., an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
FPGAs are called “field programmable” because the configuration data is written to the device each time the device is powered up (i.e., the device is programmed in the field). Other field programmable PLDs include CPLDs, for example, to which configuration data can be written once and the device remains configured until the configuration data is erased or overwritten. Thus, a CPLD can be programmed by the CPLD provider, the customer, or both. Other field programmable PLDs can include, but are not limited to, anti-fuse and fuse devices.
On the other hand, mask programmable devices such as Application Specific ICs (ASICs) are programmed by the ASIC manufacturer, by adding one or more customized metal layers as part of the semiconductor manufacturing process. Therefore, mask programmable devices are not field programmable.
As with any other integrated circuit, a field programmable PLD can include manufacturing defects. A defect too small to see can render a PLD completely or partially nonfunctional. PLD technology trends include rapidly increasing logic density. Thus, a tiny defect is more and more likely to impinge on active logic on the silicon surface of a die. Another important trend is a rapid increase in die size. As PLDs increase in size, the likelihood of a given die including a defect increases dramatically.
If a PLD die contains a single defective resource (e.g., if one of the configuration memory cells in an FPGA is defective), the PLD can render a user's end product unusable, because the user design might need to use that defective resource. To avoid problems with customers, a PLD provider generally discards a PLD if it contains even one defect that affects the active logic. Thus, a natural consequence of the increases in PLD size and density is an increase in the percentage of defective die, or a decrease in product yield. (The words “PLD provider”, as used herein, refer to an entity that designs, manufactures, or distributes a PLD, as well as to an entity that performs two or more of these functions. For example, many FPGA providers design but do not actually manufacture their own FPGAs.)
The problem of low yield has significant economic impact on PLD providers. There are two types of defects: gross defects (which cause the failure of an entire PLD) and localized defects (which cause the failure of small portions of the PLD circuitry). It has been estimated that close to two thirds of large FPGA dice are discarded because of localized defects. Therefore, it is desirable to provide methods for using field programmable PLDs having localized defects to implement user designs.
One known method for using defective PLDs is to sort out those PLDs that are defective only in an isolated function. For example, an FPGA provider can set aside all of those FPGAs in which only the block RAM is defective. If a user design does not use the block RAM, the design will still function correctly when implemented in one of these FPGAs. The FPGA provider can sell these partially defective devices to the customer at a reduced price, as an alternative to discarding them.
However, in FPGAs most defects occur in the large CLB array that occupies the majority of the die. The CLBs are largely identical to each other, and each CLB can be programmed to perform any of a very large number of functions. Therefore, unless special steps are taken, it is virtually impossible to look at a user design and say with confidence that the implementation software will not use a given CLB to implement the design.
Further, when the design is implemented, the location of the defective CLBs is generally unknown, and is different for each defective device. Hence, when a single user design is targeted to a large number of defective PLDs (e.g., when a user wants to use defective PLDs in production to reduce the selling price of the end product), it can be very difficult to ensure that the implemented design will not impinge on defective locations in any of the targeted defective PLDs.
Cliff et al., in U.S. Pat. No. 5,434,514, and Reddy et al., in U.S. Pat. No. 6,201,404 describe two similar approaches to the problem of defective logic blocks in an FPGA. (Both of these patents are incorporated herein by reference.) According to Cliff and Reddy, an extra row (or column) of logic blocks is included in an FPGA. If one or more logic blocks in the central array are found to be defective during testing, the device is permanently programmed at the factory such that the row containing the defective logic blocks becomes transparent to the user. When the FPGA is programmed with the configuration bitstream, the defective row is bypassed, while the extra row is used as a replacement.
This method has the advantage that the same configuration data file is used for defective devices and fully functional devices. However, the method also has the drawback that the timing of the implemented design in a defective device can be significantly different from the timing of the same design in a fully functional device. The extra row of logic blocks and the supporting logic and routing also consume additional silicon area, increasing the cost of the FPGA (including those that are fully functional), and further increasing the likelihood of finding defects in the die.
Another method for handling fault tolerance is described by Hanchek and Dutt in “Node-Covering Based Defect and Fault Tolerance Methods for Increased Yield in FPGAs”, Proceedings of the Ninth International Conference on VLSI Design, January 1996, which is incorporated herein by reference.
According to Hanchek's method, during the place and route process each primary CLB (node) in the FPGA is assigned a cover (i.e., replacement) CLB that can be reconfigured to replace the primary CLB if the primary CLB is defective in a particular target FPGA. The cover CLB of a particular primary CLB may be an unused CLB or another primary CLB, thereby forming a chain of primary/cover CLBs. A spare row (or column) of CLBs is provided for covering the last primary CLB in the row (or column). The FPGA routing software reserves the segments required to complete routes to the covering CLBs.
In a first approach, Hanchek alters the FPGA at the factory (e.g., by burning laser programmable links) such that the cover CLBs are used instead of the defective CLBs. In a second approach, non-volatile configuration bits on the FPGA (e.g., EEPROM memory cells) can be programmed by the user to use the cover CLBs. In either case, the same configuration data file is used for each defective and fully functional die. Also in either case, special circuitry must be included in the FPGA to accommodate the laser or EEPROM programming. The extra row or column of CLBs must also be included.
In U.S. Pat. No. 6,167,558, Trimberger describes a fault tolerance method superficially similar to Hanchek's method. (U.S. Pat. No. 6,167,558 is incorporated herein by reference.) However, Trimberger proposes altering the CLB design to facilitate shifting logic by one CLB down a row of CLBs, thus avoiding a defective CLB while having a minimal effect on design timing. Trimberger's method requires that special routing be included in the CLB to achieve this timing improvement.
While Trimberger's method has several advantages, when a user's design is implemented with the capability of using defective FPGAs, a number of “reserved resources” cannot be used to implement the design. Thus, the effective number of FPGA resources is reduced.
Logic indicates that the most efficient use of a PLD's resources is for all fully functional logic blocks to be available for implementing a user's design. One way to achieve this goal is to route the design separately for each defective PLD, avoiding all of the defective resources in that particular device, and to create a separate configuration data file for each PLD. In this case, clearly, the implementation software must have access to data pinpointing the locations of the defective logic blocks for the target PLD.
For example, an FPGA provider could supply a computer file with each defective device that pinpoints the defects for that particular device. A means for specifying resources to be “skipped” by the implementation software is already available for FPGAs. An FPGA “constraints file” can specify, for example, logic blocks (or portions thereof) in which the implementation software may not place any user logic. Thus, a corresponding constraints file could be shipped to a customer with each defective FPGA.
PLDs are sometimes used in small numbers during design development, when designs are frequently revised and re-implemented. In this type of situation, a single defective PLD could be used repeatedly, and an individualized defect data file would not be difficult to maintain for that PLD for a limited period of time.
However, where larger numbers of defective PLDs are used, maintaining the defect data files for each PLD could become a potential source of error over time. For example, the defect data file for each PLD would always have to be kept with the PLD, in case the user wanted to make changes to the design. Further, in order to take advantage of advances in the implementation software, the format of the defect data file would have to be altered periodically as the implementation software evolved. For example, the format of an FPGA constraints file for the Xilinx implementation software has altered significantly several times in the last decade, as new versions of the implementation software have been released.
Culbertson et al. describe maintaining a defect file for multiple FPGAs used in a computer system. (See “Defect Tolerance on the Teramac Custom Computer”, Proceedings of the 5th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, April 1997, Pp. 116–123, which is incorporated herein by reference.) Various user designs are mapped into the computer system, and the defect file ensures that the defective portions of the various FPGAs within the system are not used when the designs are mapped.
Culbertson et al. created a defect list for a single system, and implemented many different user designs in the system. Therefore, the situation described by Culbertson et al. is analogous to that of mapping a customer design to a single PLD having multiple defects, rather than to the present situation, where the goal is to map a single user design many times, to each of several PLDs having defects in different locations.
Another drawback of the methods taught by Cliff and Reddy is the need to avoid relatively large logic blocks that contain defects, even if there is only a single small defect in the logic block. This situation arises because the defect avoidance information and logic are on the chip, and there is limited space on the chip to store the information and avoid the defects. This limitation leads to large redundant areas, resulting in poor efficiency. In contrast, the method of Culbertson can identify a very small defect to be avoided, because the data identifying the defect is not stored on the chip.
However, according to Culbertson's method a user must manage all the data of all the chips in use. In Culbertson's case this was not a serious issue, because multiple user designs were mapped to the same PLDs, and the defect information was unchanged and re-used for each user design. However, in a system production environment, the defect information is used only once for each PLD, and new defect information is needed for each PLD. PLD providers must provide all the relevant data on defective dice to users, and should avoid sending information on defective dice that are shipped to other users. The PLD provider must track which users have which PLDs. The users must manage an inventory of defect information, much of which quickly becomes obsolete, but must be stored in case of eventual need.
Therefore, it is desirable to provide methods enabling the efficient implementation of a single user design in multiple defective PLDs, in order to maximize resource usage in these defective PLDs while minimizing user effort.